package cn.kingshion.recursion;

/**
 * 八皇后问题的基础解法
 */
public class Queen8 {
    //定义 max 表示皇后的数量
    int max = 8;
    //定义一个一维数组来存放 皇后位置的对比 ： array = {0 4 7 5 2 6 1 3}
    //这里为什么只用一维数组呢，是因为，
    // 每一个皇后都是不可能放置在同一行中，所以
    // 按照数组顺序就就是array元素的下标即为 皇后所在的行的位置，而array的元素的值就是皇后所在的列的位置
    int[] array = new int[max];

    //定义一个变量记录总共的方案
    static int count = 0;
    //定义一个变量记录判断的次数
    static int judgeCount = 0;

    public static void main(String[] args) {
        Queen8 queen = new Queen8();
        queen.check(0);
        System.out.println("共有 "+count +" 种解法");
        System.out.println("一共判断了 "+judgeCount +" 次");
    }

    //编写一个方法，放置 第 n 个皇后
    //check方法中 ： 每一次进入递归都 有 for 循环， 每次不满足for 循环内的if 条件时候就会回溯。
    public void check(int n) {
        //当 8 个皇后都 放置好了，就直接输出
        if(n == max){
            print();
            return;
        }
        //一次放入皇后，并且判断是否冲突
        for(int i = 0;i<max;i++){
            //先把当前这个皇后 n 放到该行的第 1 列 即 第 0 个位置
            array[n] = i;
            //判断这个（第 n 个）皇后的摆放位置（第 i 列）是否跟之前已经摆放的皇后位置有冲突
            if (judger(n)) {
                //如果没有冲突，则继续后面的 第 n+1 个皇后的摆放
                check(n+1);
            }
            //如果存在冲突，那么就 继续执行 array [n] = i ;
            //即 将第 n 个 皇后放在 本行的第 i 个位置，就是不断的向后移动，知道移动到本行的最后
        }
    }

    /**
     * 放置皇后的时候的一个判断，如果当前皇后与之前已经摆放好的皇后存在冲突，则 返回 false
     * @param n 表示第 n 个皇后
     * @return
     */
    public boolean judger(int n){
        judgeCount++;
        for(int i = 0;i<n;i++){
            //说明：
            // 1、array[i] == array[n] 用来判断当前的皇后 与之前的 i 个 皇后是否处在同一列
            // 2、Math.abs(n-i) == Math.abs(array[n]-array[i])  用来判断 第 n 个皇后 是否和 第 i 个皇后处于同一斜线
            // 例如： n = 1 放置第 2 列
            // 3、判断是否在同一行，没必要每次 n 都在递增
            if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n]-array[i])){
                return false;
            }
        }
        return true;
    }

    /**
     *  输出皇后摆放的位置
     */
    public void print(){
        count++;
        for (int i = 0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
}
